%Notes:
% anytime a \begin{thing} is used, there needs to be a corresponding \end{thing}
% double quotes are done by using two single quotes

%states the different types of class
%article is being used because of the weird numbering system on the other
%classes, so titlepage has to explicitly stated in this class
\documentclass[titlepage]{article}

%this says to use times as a style and to indent the first paragraph because it 
%does not do that by default
\usepackage{times, indentfirst}

%this allows graphics to be added
\usepackage[pdftex]{graphicx}

%this package is to allow the following \restylefloat which is an override
%that allows the user to explicity state formatting with figures (images)
\usepackage{float}
\usepackage[T1]{fontenc}

\restylefloat{figure}

%the following three lines are all for the title and the various \huge, etc are different font
%sizes and there is a difference between \Huge and \huge
%\\* is the escape for new line
\title{\Huge CSE325 Lab 6 File System}
\author{\huge Group 4: \\*  \LARGE Matthew Cramer, Jesse Martinez, Marc Mendoza}
\date{\LARGE \today}

%needed to start the document, think of it like main in normal programming
\begin{document}
%creates the title page based on \title, \author, \date
\maketitle

%this labels a section and it will be numbered in the paper, there is a hierarchy to
%the levels of sections, and curly braces are required
\section{Introduction}
This lab documentation will be describing the manager for a file system that can support a device and format a file system on it to do file management for the Operating System.  This documentation will explain the File System manager and how it intends to be implemented and controlled with different functions called from a Testing Interface.  This documentation will give a state diagram for the different states that a File System can be in at a given time and a activity diagram to see the different approaches the manager takes to be in these states.  

The functions available in the manager are also described and how they work with the Testing Interface.  Since the manager will be implementing a virtual hard disk for the assignment, the hard disk will be described for the file system and the File Control Blocks (FCB) used in the system.  Finally, a test plan will be described that will explain how each part of File System manager will be tested and implementation decisions are described that were made for this project.


\section{File System}
This assignment implements a file system that works based off of a virtual hard drive in the system.  The Testing Interface passes commands to the File System manager and carries out the functions defined in the system.  Below is a state diagram (Figure 1) of the different states a file system can be in.  Also defined is the functionality of the file system and what takes place when each function occurs.  This layout in figure 2 is described in section 2.1 of what the functions are and how they are used with the overall program and the Testing Interface.  

\begin{figure}[H]
\begin{center}
\includegraphics[scale=.5]{StateDiagram.jpg}
\caption{State Diagram for File System}
\end{center}
\end{figure}

This state diagram is for the file system and all errors are handled by the file system manager. The several states for the file system is device known, file system created, and file system mounted. The first state is when the system is initialized the device becomes known. Then the file system is formatted and the file system is created. The file system is then mounted on the system to be used and the file system is terminated when the system is terminated.  If there are any problems along the way of initializing a device, formatting a file system or mounting it, the system will enter an error state and terminate.

\begin{figure}[H]
\begin{center}
\includegraphics[scale=.5]{StateDiagram1.jpg}
\caption{State Diagram for File System Block of Memory}
\end{center}
\end{figure}

The above state diagram (figure 2) shows the states for a block of data on the file system.  When the program initiates, the block is created but enters an unused state where it is not allocated to any data or file system.  When the device gets initiated, the block gets used by the device but is not allocated to any data, and is therefore in an unallocated state.  Once the files system gets formatted, the block will become allocated for the file system but will initially not contain any data, thus it will be empty.  At this state, the system can terminate which will end the program or it can write data to a block.  When data is written to it, the block will become allocated and valid, indicating it contains actual data for the file system.  From here, the block can be erased indicating it is not longer being used for data and will return to an empty state.  However, if the valid block becomes corrupted, the block will enter an Allocated Bad state.  If the block is correctable, it will be corrected and return to a Allocated Valid state.  If it cannot be corrected, it will become an Unusable block and then that block will be removed from the File System's reach.

\begin{figure}[H]
\begin{center}
\includegraphics[scale=.7]{FlowDiagram1.jpg}
\caption{Flow Diagram for File System}
\end{center}
\end{figure}

\begin{figure}[H]
\begin{center}
\includegraphics[scale=.5]{FlowDiagram2.jpg}
\caption{Flow Diagram for File System}
\end{center}
\end{figure}

\subsection{File System Functions}
Below are descriptions for the different functions in the file system manager and how they work with the Testing Interface to carry out commands.  These functions work with the flow diagram in Figure 3 and Figure 4 to describe the flow of the program for each command.  
\begin{enumerate}
\item{\bf init\_fs device}

When the File System receives the command to initialize a device, it will create the necessary allocation in the system for the pointers to the new device being initialized. For this project, we are only allowing one device to be initialized at a time.  When the device is initialized, a device header will be created on the Hard Disk in a frame that will keep track of the file systems on it.  Since for this project only one file system is going to be on a device, the device header will be pointing to where the file system header will be once it gets formatted.  This device's name will be stored in the Testing Interface in an array and the File System manager will get passed a reference number for that Device's name that gets assigned in the Testing Interface.    

\item{\bf list\{DEVICES | FILEINFO filename | DIRECTORY directory\_name\}}

When the manager gets the command to list the contents of certain criteria from the Testing Interface, there are many options that can be taken to be displayed.  If a listing of devices (DEVICES) is requested, it will return the name of the device mounted on the system if there is one.  If a listing is requested of a certain file name that is currently opened in the File System (FILEINFO), then it will return the FCB's for that file back to the Testing Interface to be displayed.  If the DIRECTORY listing is requested, it will locate the directory headers in the file system that keeps track of where all the valid files are kept for that directory and return the directory headers to the Testing Interface to parse through it. If there is a directory name given in the arguments, it will just display the files listed in that directory if it exists.   If just the list command is issued from the Testing Interface, all the above commands will be issued for all devices, directories and files.  

\item{\bf format device fs\_name blocksize}
When the format function is called from the Testing Interface, it will allocate a new file system on the device with the supplied name and the block size from the Testing Interface. This will be done by allocating a block in the Hard Disk as a file system header that will indicate that a file system has been formatted on this device.  The array in the FCB for that file system header will be pointing to what directories are associated with that file system.  If the block size can be issued for this file system, it will allocate block sizes for the file system on the specified device and report back to the Testing Interface the number of blocks issued for this file system.  The program will determine the file size for the file but will be constant for all files for simplicity.  If the block size could not be accommodated for device, then it will return an error to the Testing Interface.  For this assignment, the block size will be requested of the same size of the frame of 4KB.

\item{\bf mount fs\_name}

This function will mount the file system to the System if the requested file system has been formatted on the device.  This will be done by indicating with variables in the FCB that the file system is now being used and mounted to the system.  It will return an error if the file system does not exist on the device and has not been formatted.  

\item{\bf create\_directory directory\_name}

This command is not on the requirements for the assignment but was implemented to account for the extra credit that is being done in the program.  Since for this assignment directories are being implemented, this function will create directories to be used.  It requires a unique name for a directory that will be used in the file system.  The Testing Interface will determine the uniqueness of the name of the directory.  The creation of the directory will create a directory header in the file system and a pointer will be allocated in the file system header indicating that there is a new directory in the file system.  For this assignment, there will only be one layer of directories for simplicity.  A directory must be created before any files are created and files must be placed in an existing directory.  

\item{\bf open directory\_name filename [new | read-only | read-write]}

This command will deal with file management of a file that is to be used on the file system that is mounted on the system from a device.  A directory must be specified to create the file in that directory.  For this project, there will only be one layer of directories in the file system and a file must be created in one of those directories.  The file name that is supplied with this command will be given a unique file handle number in the Testing Interface in order to not deal with strings in the File System manager.  The file handle for this file will be sent to the File System manager and will be applied with the options it is given with and used with the other commands when trying to reference this.  The file handle will be placed in the ID field of the FCB.     

If the file is to be created for the first time with the "new" option, it will allocate a file with the given file handle on the file system mounted. The Testing Interface will handle string comparisons to see if the given file name has already been used in the file system since string comparisons are easier in the Testing Interface.  For this project, each file name is unique to the system.  If the file is already being used, the it will report an error and not overwrite the file or change the permissions of the file specified.

If the specified file name is requested to change file permissions to read only with the "read-only" option, then the Testing Interface will first check to see if the file is currently being used in the file system.  If it is not, an error will be issued.  If the file does exist, then it will set a flag for the file in the FCB indicating that the file cannot be changed with the write command but only read.

If the file name requested is supplied with the permission to be read-write, then it will also ensure that the file exists first.  If it does not, an error will occur.  If the file does exist, it will set the permissions with a flag in the FCB for the file indicating that it can be read and written to by the system.  

\item{\bf read directory\_name filehandle block\_number buf\_ptr}

If the read command is issued from the Testing Interface, the File System manager will receive the file handle in the specified directory, block number and which buffer pointer to use for the read.  The file handle will be valid if the Testing Interface matches the file handle to the current file names in the system and then the file system manager will ensure that teh file is open.  If it is not valid in the specified directory or if the file is currently in the "new" permission with no read access, it will return an error.  If the file is currently open and has read access, it will look to see if the specified block number is being used within the file.  If it is not, it will return an error.  If it is valid, the manager will use the specified buffer pointer in the simulated device control, if it is valid, to fill the buffer with data from the block in the file and return that to the Testing Interface to be displayed.  The read function will work with the device controller that is being simulated to place the data in the buffer being specified.  
\newline
\newline
\item{\bf write directory\_name filehandle block\_number buf\_ptr}

If the write command is called from the Testing Interface, the File System manager will receive the arguments from the Testing Interface.  These arguments will be the file handle and the directory to look for it in, block number and buffer pointer to be used for this action.  As before, the manager will ensure that the file handle is valid in the specified directory and has read-write access to it.  If the file handle does not exist of the file does not have write privileges, an error will be returned.  Once the file has been found in the specified directory and is the right permission, the manager will look to see if the block number can be written to using the specified buffer pointer if it exists.  If the pointer does not exist, and error will occur.  The write function will work with the device controller that is being simulated to place the data in the buffer being specified.

\item{\bf close directory\_name filehandle}

This function will receive the file handle from the Testing Interface to be closed.  If the file handle does not exist in directory specified, and error will be returned.  If the file handle is found, it will set the valid flag in the FCB for that file header indicating that it is now closed.
  
\item{\bf delete directory [filename]}

This function will delete a directory or a file specified in a directory with the specified name in the file system. If there is one argument for delete, then it will be a directory name that wants to be deleted.  This delete will delete all the files associated with that directory as well freeing up all the memory from the directory and those files.  If there are two arguments, the first being the directory and the second a file in that directory, then it will delete that file if it exists. The Testing Interface will determine if the file exists using string comparisons.  If the file does exist, the file handler for that file will be passed to the Testing Interface and will then be located in the File System.  Once found, the manager will free the memory being used by that file and give it back to the hard disk.

\item{\bf unmount fs\_name}

This function will unmount the file system from the system if the requested file system has been formatted on the device and mounted.  This will be done by indicating with variables in the FCB that the file system is no longer being used and not mounted to the system.  It will return an error if the file system does not exist on the device and has not been formatted or is not mounted. 

\item{\bf bad\_block block\_num}

This function was added to the assignment in order to implement a bad block instance simulating if a block on a hard disk ever got corrupted and the data needed to be placed in a new block.  This function will make the specified block number on the hard drive go bad with the badBlock bit and transfer the data to a new block that will be referenced by the bad block if there is no valid data.  This is done by transferring the data with a buffer pointer and placing it in one of the set aside blocks in the hard disk for bad blocks.  

If the block is a directory header, the data for the files will be transfered to another memory block and reconnect the files to the directory.  This will also recursively go to each file and set their parent pointer to the new directory location.  The same with a file header, the new block will contain the pointers to the file blocks and the blocks will contain pointers to the new block location. This function can be confirmed when the data for a file is displayed with the list command indicating that the bad block created is now at a different location in the hard disk.  If the file is not valid in the specified directory or the block number is out of range of the file, the File System manager will report an error.  

For this function, if the data has been lost due to the data block being corrupted and is not recoverable, the system will report and error indicating that it cannot recover from this error.  For this project, when the data block is unrecoverable, the system will delete the whole file that has been corrupted by this bad block.  This design decision was made to simply dealing with bad blocks and just delete all the data for it.

\end{enumerate}

\subsection{File Control Block (FCB)}
\begin{enumerate}

\item{\bf frameType}

This field is used for specifying if the frame of memory is a directory header(1), file header(2), fileblock(3), device header(4), or file system header(5).

\item{\bf ID}

This field is where the filehandle or directory number is stored.

\item{\bf parentPtr} 

This field points to the parent of the block.  This could be the directory head for a file header or the file header for the file blocks, depending on what the frameType is.

\item{\bf badBlock}

This field will be used to indicate if the block is a Bad Block.  This is more of a hardware then software issue because of the physical limitations of the hard drive.  Since there is no actual hardware being using in this program, we will be simulating errors on the hard disk with the bad\_block function.  If the bit is -1, then the block is not bad.  If the bit is 0, then the block has been marked as a bad block.  If the bit is positive, then the block has been readdressed to a new block and the bit indicates the index on the hard disk of the new allocated block for this bad block.  

\item{\bf  permission}
This field is where we specify the permission of what each file is where 0 is a new file, 1 is a file that can be read, and 2 is a file that has read/write access.

\item{\bf nextIndex}

This field is used for the implementation of the linked list and will point to the next frame in the list for the virtual hard disk.

\item{\bf prevIndex}
 
This field is used for the implementation of the linked list and will point to the previous frame in the list for the virtual hard disk. 
 
\item{\bf pointers}

This field will be an array inside our FCB structure that will show all the file block locations for the file header or all the locations of the files for a directory header. This field will have a new structure called PointerArrayBlock. This structure will contain the filehandle number of the file or directory, the location of the file or directory in memory, and a valid bit which will be -1 if it's a directory, 0 if the file is open, and 1 if the file is closed. 

\item{\bf ptrSize}

This field will be used for the size of the array that is being used to store files and directories so we do not cycle through all the frames but just the frames that are being used for this particular header.

\item{\bf Data}

This field will be where data of the file is held. This data field will only be used when the frameType is a fileblock and is not actual data since no real data is in the system.

\item{\bf fileSystem}

This field will specify if the device has been formated with a file system.   This bit is only used for the File System header on the hard disk.  If the filesystem bit is 0, then the file system is not formated while if the bit is 1, then the file system is formated.

\item{\bf Mounted}

This field will specify if the drive is mounted or not to the system from a device.  This is only used in the device header. 0 will specify that the drive is not mounted and 1 will specify that the drive is mounted.


\end{enumerate}

\subsection{Run Time}
The run time of the file system is O(n) because we are using a linked list and pointers to make all the searches constant time and with a empty space list adding new files or directories there is no search time to find an empty spot so this is constant as well. 
The only function we have that will go through the entire array is the list function which will list all directories and files inside our file system. 

\section {Testing Plan}
Tests were conducted by sending commands to the File System from a Testing program.  This testing program tested the capacity and integrity file system in the File System Manager by expecting values back from the manager.  If the return values were what it expected, the test passed.  For the functionality of the Testing Interface, such as handling the user input and arguments for the commands, expected output samples were generated and compared with the actual output from the Testing Interface that are executed in the script file.  This was done by string comparison of the two output files in order to see if the correct output was given for each functionality test. The testing files are located in their own sub folder "TestingInterface/Tests".

To compile the Test program, run the "compileTests.sh" script and finally execute "runTests" to run the testing program.  The program will list the tests run and if they passed or not.  

\subsection {Capacity}
\subsubsection{Empty Hard Drive}
This test will ensure that when the file system is formatted, there is no data in the file system and will call the different list functions to ensure all the error statements are displayed correctly.

\subsubsection{Max Hard Drive}
This will ensure that the maximum number of files can be created. The test will create files until the max number of files is made and then all files are listed with the list command to check that all files are created properly under directories.

\subsection {Functionality}
\subsubsection {init\_fs}
This test will check that the file system manager knows about the device and there is nothing else on the hard disk yet.  It will also ensure that only one device can be initiated and that if init\_fs is called again, it will clear the entire hard disk of data and reset it for the new device.  This test will also make sure the arguments are checked correctly for this function and return the proper errors if not. 

\subsubsection {list}
This will ensure that when the list function is called, that it will list all devices, all file FCBs, and all valid files in the filesystem. If an argument is given it will check to see if it is the right type of argument, being devices, fileinfo [filename], or directory. If the argument is not a corresponding argument, it will report the error. If it is, it will display the device known to have valid file system, the FCB of a specified file, or list information about all valid files in the file system under valid directories.  The list function will also ensure that if bad blocks have been located on the hard disk, it will show the new location of the block under the FCB for the file block that failed.  

\subsubsection {format}
This test will ensure that the device is formatted properly to the specified size and the name specified is associated with the device.  It will also ensure that only one file system is formated for the one device.   This test will also make sure the arguments are checked correctly for this function and return the proper errors if not. 

\subsubsection {mount}
This test will ensure that the internal system structures is allocated properly for the file system and that the correct FCB is changed.  This test will also ensure that none of the file commands can be used since the file system is not mounted.  

\subsubsection {open}
This test will ensure that the argument supplied with the open function performs the proper corresponding action and that the specified file is the file that is opened and located in the specified directory.  It will also ensure all the correct arguments are given and used correctly.  

\subsubsection {read}
This test will check that the correct file is being read from in the specified directory, the proper block is read, and the block is placed in the buffer properly in the hardware simulated portion of the device controller.  This test will also make sure the arguments are checked correctly for this function and return the proper errors if not. 

\subsubsection {write}
This test will check that the correct file is being written to in the specified directory, the proper block is written, and the block is placed in the buffer properly in the hardware simulated portion of the device controller.  This test will also make sure the arguments are checked correctly for this function and return the proper errors if not. 

\subsubsection {close}
This test will check the FCB of the file being closed is properly updated and that the file exists.  This test will also make sure the arguments are checked correctly for this function and return the proper errors if not. 

\subsubsection {delete}
This test will check that the correct directory and/or files are deleted and the memory is properly returned to the free pool of blocks on the hard disk.  This will be done by checking pointers of header blocks that they were properly reset.  This test will also make sure the arguments are checked correctly for this function and return the proper errors if not. 

\subsubsection {unmount}
This text will check to see if a file system is mounted then unmount it by setting the mount bit in the file system header to unmount.  This will be confirmed by trying to do functions with the file system which will not be allowed since the file system is not mounted. This test will also make sure the arguments are checked correctly for this function and return the proper errors if not. 

\subsection {Extra Credit Tests}
\subsubsection {bad\_block}
Bad blocks will be tested by making bad blocks in memory and making sure that the back up memory will be referenced by the bad blocks correctly using pointers.  This will be done by calling the function and using the list function to ensure the address of the block has now changed to the new block.  It will also check to ensure that if a allocated valid block is set to a bad block, that the whole directory or file be deleted.  This test will also make sure the arguments are checked correctly for this function and return the proper errors if not. We are keeping the bad block code inside the program but it is all commented because we never had time finish the implimintation of bad block out so please do not use. 

\subsubsection {create\_directory}
This test will ensure that once a file system has been mounted, that a directory be created first before any files can be created, since each file has to be in a directory.  This test will ensure that the file system knows about all the directories and assign the right files to each directory.  his test will also make sure the arguments are checked correctly for this function and return the proper errors if not. 

\section{Misc. Design Decisions}
\subsection{File System}
The file system will be broken down into blocks where each block is 4KB, corresponding to the size of the frame on the hard disk.  This was done to make the program more simplistic and not have to deal with multiple blocks in one frame. The Testing Interface will always ensure that 4KB is asked for the block size. The size of the hard disk is 256MB or 65,536 blocks.  Blocks 0-267 on the hard disk will be set aside for various system headers when the system is formatted.
\begin{enumerate}
\item 0-9: These blocks are set aside for the buffers, making a total of 10 buffer blocks to be used for the simulated device controller and the read/write operations.  This was done to store everything needed for the file system on the device and 10 of the blocks on the hard disk for buffer space.
\item 10-265: These blocks are set aside for bad block space to be used to replace bad blocks on the file system.  
\item 266: This block will be the device head and contain pointers to the file system head.  Since when we initialize the device first in the Testing Interface, this block will always be allocated at this index since that is being controlled in the file system manager.  The file system must always be formatted after the device is known and therefore will always point to the next block location in the hard disk for the file system head.  For this assignment, if this block becomes bad, the File System manager will report that the device header has corrupted and the hard disk has crashed. 
\item 267: This block will be the file system head and will contain pointers to the directories in the file system.  As above, if the file system header goes bad, the file system manager will indicate that the file system has been lost and will need to be reformatted.  
\item Various blocks will contain directory heads that will contain pointers to the file heads of the files contained in those directories.
\item Various blocks will contain a file head that will contain pointers to the data blocks of the file.
\item Various blocks will contain the file blocks that are being used by open files in the system.
\end{enumerate}

\subsection{File Creation}
When files are created, the file is given a maximum size limit of 4MB which is 1024 frames.  Once created, write functions will write to the data blocks in the file and allow the file to grow dynamically as the file get written to to the maximum limit. There will also be a maximum count of 60 files that can be allocated on the hard disk. This was done to ensure that the hard disk never hits full capacity with files and the blocks can be allocated enough for each file.  Since the Testing Interface did not specify what file size to use, it was created to be static for all files. 

\subsection{Hardware Stub for implementing Device Controller}

The hardware for the file system is going to be for the read and write functions to use the buffer spaces and hard disk.  This will be placed in the program to simulate the hardware for a device controller.  The other hardware that is required for the file system is for a Bad Block because the software will need to specify what blocks are bad and need to be fixed.  The hardware for the bad block will be inside the FCB so the system will know what blocks of memory will not work and need to be fixed.  This is taken care of in the bad\_block function. 

\subsection{Device as Hard Drive}
For this project, it was decided to have the device that connects to the system be a hard drive only.  This is to keep it consistent with the blocks that are allocated in a hard drive fashion and to keep the project simplistic.  Ever device connected will be considered a hard drive and the file system will be created and mounted to the system accordingly.  

\subsection{Formatting Device}
For the simplicity of the program, a device can only be formatted once in this program. If the Testing Interface calls to reformat a device that has already been formatted, it will error and ask to reinitialize the system with a new device where the old one will be lost.

\subsection{Queue Manager}
This project also includes the Queue Manager from the previous labs and implements the hard drive blocks as a linked list.  The Queue Manager will handle enqueing and deleting blocks from the hard drive list by passing the parameters for each block to and from each portion of the code accordingly.  

\subsection{Extra Credit}
\subsubsection{Bad Blocks}
Bad blocks will be fixed by replacing the bad blocks with back up memory. The back up memory is part of the 256MB from the hard disk.  When one of the blocks become a bad block, the back up memory will point to where the bad block is and be used to store the
file or data that should go into the bad block of memory. This will allow the user to never know there is a bad block because the block will go into the back up data instead. Since there is a limit of back up memory if there are more bad blocks then back up memory a error message will be presented, but in the file system there is enough back up for all the bad blocks.  In order to show the bad block is being used, the memory locations of the bad block and the new block will be displayed for the list command.  If there is essential data in the bad block and the bad block becomes unrecoverable, the system will delete the whole file or directory depending on the block type.  This was done to simplify the process of correcting for bad blocks and just delete the file in general to indicate a hard drive failure and corrupted file on the system.
\subsubsection{Directories}
Directories will be implemented using a root level system. This means that all directories will only be made at the root level and files can only be created within the directories.  This was done to implement a directory structure but not have multiple levels for simplicity of the program.  Since the assignment is to focus on the required aspects, the directory levels was simpled to focus on those aspects.  

\end{document}